package leetcode;
/***
 * 题目：打家劫舍
 * 链接：https://leetcode.cn/problems/house-robber/?envType=study-plan-v2&envId=top-100-liked
 */
public class Rob {
    public static void main(String[] args) {
        int[] nums = {5,8,8,7};
        int maxSum = rob(nums);
        System.out.println("maxSum = " + maxSum);
    }
    /**
     * 动态规划
     */
    public static int rob(int[] nums) {
        int[] dp = new int[nums.length];
        if(nums.length == 0) return 0;
        // 开始按规则求值
        for (int i = 0; i < nums.length; i++) {
            if (i == 0) dp[0] = nums[0];
            else if (i == 1) dp[1] = Math.max(nums[0], nums[1]);
            else dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[nums.length - 1];
    }
}
